# -*- coding: utf-8 -*-
import math;

# 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）
# 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）
# 问总共有多少条不同的路径？

# 说明：m 和 n 的值均不超过 100

# 示例 1:
# 输入: m = 3, n = 2
# 输出: 3
# 解释:
# 从左上角开始，总共有 3 条路径可以到达右下角
# 1. 向右 -> 向右 -> 向下
# 2. 向右 -> 向下 -> 向右
# 3. 向下 -> 向右 -> 向右

# 示例 2:
# 输入: m = 7, n = 3
# 输出: 28








# 动态规划的思路解决问题
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m == 1 or n == 1:
            return 1;
        checkerboard = [[1] * n for _ in range(m)];

        for i in range(1, m):
            for j in range(1, n):
                checkerboard[i][j] = checkerboard[i - 1][j] + checkerboard[i][j - 1];

        return checkerboard[-1][-1];



# 走m + n - 2步肯定能到达终点，其中向下m - 1步，向右n - 1步
# 是一个排列问题
# 啊！！该补一补排列和组合相关的内容了
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        return math.factorial(m + n - 2) / math.factorial(m - 1) / math.factorial(n - 1);


t = Solution();
print t.uniquePaths(7, 3);